package algorithm;

/**
 *  接雨水
 */
public class RainWater {


    /**
     * 暴力算法 时间复杂度O(N^2) , 空间复杂度O(1)
     * @param arr
     * @return
     */
    public long maxWater(int[] arr){
        int ans = 0;
        for (int i = 1 ; i < arr.length - 1; i++) {//第一个柱子和最后一个柱子肯定解不了雨水，不用计算
            int leftMaxH = 0;
            int rightMaxH = 0;
            for( int j = i ; j >= 0 ; j --){
                leftMaxH = Math.max(leftMaxH , arr[j]);//计算当前柱子左边的最高的柱子的高度
            }
            for (int j = i ; j < arr.length ; j ++){
                rightMaxH = Math.max(rightMaxH , arr[j]);//计算当前柱子右边的最高的柱子的高度
            }
            ans += Math.min(leftMaxH , rightMaxH) - arr[i];//当前柱子的存水量取决于左边和右边最高柱子中，较低的那个。并减去当前柱子本身的高度
        }

        return ans;
    }

    /**
     * 双指针算法 时间复杂度O(N) 空间复杂度O(1)
     * @param arr
     * @return
     */
    public long maxWater1  (int[] arr){
        long ans = 0;
        int left = 0;//左指针
        int right = arr.length - 1;//右指针
        int leftMaxH = 0;
        int rightMaxH = 0;
        while (left < right){
            if (arr[left] < arr[right]){//左指针所指柱子的高度小于右指针所指柱子的高度
                if (arr[left] > leftMaxH){
                    leftMaxH = arr[left];//记录柱子高度的最大值
                } else {
                    ans += leftMaxH - arr[left];//左右指针之间柱子的接雨水量取决于左指针所指柱子的高度
                }
                left ++;//从左向右移动左指针
            } else {//否则，如果右指针所指柱子的高度小于左指针所指柱子的高度，那么左右指针之间柱子的接雨水量取决于右指针所指柱子的高度
                if (arr[right] > rightMaxH){
                    rightMaxH = arr[right];
                } else {//如果当前柱子高度小于最大值，则当前柱子可以接雨水为柱子高度的最大值减去当前柱子高度
                    ans += rightMaxH - arr[right];
                }
                right --;//从右向左移动右指针
            }
        }

        return ans;
    }
}
